#pragma once
#include<iostream>
#include"AdjacencyMatrix.h"

// Nn <- p <-> N1 <-> N2 ..... <-> Nn <-> p
typedef struct Queue {
	int index;
	Queue* next;
	Queue* pre;
}Queue;

void InitQueue(Queue*& q) {
	q = (Queue*)malloc(sizeof(Queue));
	q->next = q;
	q->pre = q;
}

bool IsQueueEmpty(Queue* q) {
	if (q->next == q) {
		return true;
	}
	return false;
}

void EnQueue(Queue* q, int index) {
	Queue* qNode = (Queue*)malloc(sizeof(Queue));
	qNode->index = index;
	qNode->pre = q->pre;
	qNode->next = q;

	q->pre->next = qNode;
	q->pre = qNode;
}

Queue* DeQueue(Queue* q) {
	if (IsQueueEmpty(q))
		return NULL;

	Queue *qNode = q->next;

	q->next->next->pre = q;
	q->next = q->next->next;

	qNode->next = NULL;
	qNode->pre = NULL;
	return qNode;
}


void BFS(Graph* graph, int* isVisited, int index) {
	printf("%c ", graph->vertices[index]);
	isVisited[index] = 1;

	Queue* q;
	InitQueue(q);
	EnQueue(q, index);

	while (!IsQueueEmpty(q)) {
		Queue* qNode = DeQueue(q);
		for (int i = 0; i < graph->verNum; i ++) {
			if (!isVisited[i] && graph->edges[qNode->index][i]) {
				//当前节点 qNode 所在邻接矩阵 行 / 列 中的节点
				//1. 是否被访问
				//2. 是否与当前节点有连接关系
				printf("%c ", graph->vertices[i]);
				EnQueue(q, i);
				isVisited[i] = 1;
			}
		}
	}
}
